package binarysearch;

import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        int[] arr = new int[10];

    }

    public int InversePairs (int[] nums) {
        // write code here
        recursion(nums, 0, nums.length - 1);
        return count;
    }
    private void recursion(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        recursion(nums, left, mid);
        recursion(nums, mid + 1, right);
        merge(nums, left, right);
    }
    int count = 0;
    private void merge(int[] nums, int left, int right) {
        int mid = (left + right) / 2;
        int s1 = left;
        int s2 = mid + 1;
        int len = right - left + 1;
        int[] tmp = new int[len];
        int index = 0;

        while (s1 <= mid && s2 <= right) {
            if (nums[s1] < nums[s2]) {
                tmp[index++] = nums[s1++];
            } else {
                tmp[index++] = nums[s2++];
                count = (count + mid - s1 + 1) % 1000000007; // 奥秘
            }
        }

        while (s1 <= mid) {
            tmp[index++] = nums[s1++];
        }

        while (s2 <= right) {
            tmp[index++] = nums[s2++];
        }

        for (int i = 0; i < len; i ++) {
            nums[left+i] = tmp[i];
        }
    }
}
